package com.cwl.arithmetic;

/**
 * @program: data-structure
 * @description: 快速排序
 * @author: ChenWenLong
 * @create: 2019-11-15 10:32
 **/
public class QuickSort {

    /**
     * 功能描述:
     * 〈对指定数组进行分割〉
     *
     * @params : [a, p, r]
     * @return : int
     * @author : cwl
     * @date : 2019/11/15 9:42
     */
    private static int partitionInt(int a[],int p,int r){
        int x = a[r-1];
        int i = p - 1;
        int temp;
        for(int j=p;j<=r-1;j++){
            if(a[j-1]<=x){
                i++;
                temp = a[j-1];
                a[j-1] = a[i-1];
                a[i-1] = temp;
            }
        }
        temp = a[r-1];
        a[r-1] = a[i];
        a[i] = temp;
        return i+1;
    }

    /**
     * 功能描述:
     * 〈快速排序方法〉
     *
     * @params : [a, p, r]
     * @return : void
     * @author : cwl
     * @date : 2019/11/15 9:42
     */
    public static void quickSortInt(int a[],int p,int r){
        if(p < r){
            int q = partitionInt(a, p, r);
            quickSortInt(a, p, q-1);
            quickSortInt(a, q+1, r);
        }
    }
}
